﻿// 171. 送礼物  jinjiezhinan.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <algorithm>


using namespace std;

/*

https://www.acwing.com/problem/content/173/
达达帮翰翰给女生送礼物，翰翰一共准备了 N 个礼物，其中第 i 个礼物的重量是 G[i]。

达达的力气很大，他一次可以搬动重量之和不超过 W 的任意多个物品。

达达希望一次搬掉尽量重的一些物品，请你告诉达达在他的力气范围内一次性能搬动的最大重量是多少。

输入格式
第一行两个整数，分别代表 W 和 N。

以后 N 行，每行一个正整数表示 G[i]。

输出格式
仅一个整数，表示达达在他的力气范围内一次性能搬动的最大重量。

数据范围
1≤N≤46,
1≤W,G[i]≤231−1
输入样例：
20 5
7
5
4
18
1
输出样例：
19


73 7
13
29
150
23
17
16
1

70
*/

const int N = 50;
int arr[N];
int w, n;
int sum[1 <<24]; int sumIdx;
int ans = 0;

void dfs2(int idx, int curr) {
    if (curr > w) return;
    if (idx == n) {
        int l = 0; int r = sumIdx - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (sum[mid] + (long long )curr <= w) {
                l = mid;
            }
            else {
                r = mid - 1;
            }
        }
        if (sum[l] + (long long)curr <= w) {
            ans = max(ans, sum[l] + curr);
        }
        
        return;
    }

    if ((long long)curr + arr[idx] <= w) {
        dfs2(idx + 1, curr + arr[idx]);
    }

    dfs2(idx + 1, curr);
    
}

void dfs1(int idx, int curr) {
    if (idx == (n / 2)) {
        if(curr <= w){ sum[sumIdx++] = curr; }
        return;
    }
  
    if ((long long)curr + arr[idx] <= w) {
        dfs1(idx + 1, curr + arr[idx]);
    }

    dfs1(idx+1,curr);
   
}

void RmDup() {
    int i = 0; int real = 0;
    for(int i = 0;i < sumIdx;){
        while (i != sumIdx - 1 && sum[i] == sum[i + 1]) { i++; }
        { sum[real] = sum[i]; real++; i++; }
    }
    sumIdx = real ;
}


int main()
{
    cin >> w >> n;
    for (int i = 0; i < n; i++) { cin >> arr[i]; }
    //sort(arr, arr + n);
    //reverse(arr, arr + n);
    dfs1(0, 0);
    sort(sum,sum+sumIdx);
    RmDup();

    dfs2(n / 2 , 0);
    cout << ans << endl;
    return 0;
}

 